package com.jjlin.chapter_3;

import java.util.*;
public class CD173{
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    //判断数组nums是否为搜索二叉树的后序遍历
    public static boolean isPostArr(int[] nums){
        if(nums == null)
            return false;
//         return isPost(nums, 0, nums.length - 1);
        return isPost1(nums, 0, nums.length - 1);
    }

    //自己的写法：判断nums[start..end]是否为二叉搜索树的后序遍历
    public static boolean isPost(int[] nums, int start, int end){
        if(start >= end)
            return true;
        //start < end
        int root = nums[end];
        int less = start;
        while(less < end && nums[less] < root)//找到第一个小于endNum的数字num[less - 1]
            less++;
        if(less == end)//nums[start...end-1]全部小于root，即没有右子树
            return isPost(nums, start, end - 1);
        else{
            int more = less;
            for(int i = more; i < end - 1; i++)//判断nums[less...end-1]是否全部大于root，没有则不是搜索二叉树
                if(nums[i] > root)
                    continue;
                else //不是搜索二叉树
                    return false;
            return isPost(nums, start, less - 1) && isPost(nums, less, end - 1);//判断左右子树是否为搜索二叉树
        }
    }

    //书本的写法
    public static boolean isPost1(int[] nums, int start, int end){
        if(start >= end)
            return true;
        int less = -1;
        int more = end;
        for(int i = start; i < end; i++){
            if(nums[end] > nums[i])
                less = i;
            else
                more = more == end ? i : more;
        }
        if(less == - 1 || more == end)
            return isPost1(nums, start, end - 1);
        if(less != more - 1)
            return false;
        return isPost1(nums, start, less - 1) && isPost1(nums, more, end - 1);
    }

    //根据后序数组重建搜索二叉树
    public static Node posArrayToBST(int[] nums){
        if(nums == null)
            return null;
        return posToBST(nums, 0, nums.length - 1);
    }

    public static Node posToBST(int[] nums, int start, int end){
        if(start > end)
            return null;
        Node node = new Node(nums[end]);
        int less = -1;
        int more = end;
        for(int i = 0; i < end; i++){
            if(nums[end] > nums[i])
                less = i;
            else
                more = more == end ? i : more;
        }
        node.left = posToBST(nums, start, less);
        node.right = posToBST(nums, more, end - 1);
        return node;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++)
            nums[i] = sc.nextInt();
        System.out.println(isPostArr(nums));
    }
}
